package edu.cityu.cs.hk.datastructures;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Comparator;
import java.util.Random;
import java.util.Arrays;
/**
 * Class containing various sorting algorithms.
 *
 * @author Michael Goodrich, Roberto Tamassia, Eric Zamore
 */
public class Sort {
  //begin#fragment mergeSort
  /**
   * Sort the elements of list L in nondecreasing order according
   * to comparator c, using the merge-sort algorithm.
   **/
  public static void mergeSort (List L, Comparator c) {
    int n = L.size();
    if (n < 2) 
      return;  // the list L is already sorted in this case
    // divide
    List L1 = new NodeList(); // first list used in recursion
    List L2 = new NodeList(); // second list used in recursion
    int i = 0;
    while (i < n/2) {
      L1.insertLast(L.remove(L.first())); // move the first n/2 elements to L1
      i++;
    }
    while (!L.isEmpty())
      L2.insertLast(L.remove(L.first())); // move the rest to L2
    // recurse
    mergeSort(L1,c);
    mergeSort(L2,c);
    //conquer
    merge(L1,L2,c,L);
  }
  //end#fragment mergeSort
  
  //begin#fragment merge
  /**
   * Merge two sorted lists, L1 and L2, into a sorted list L.
   **/
  public static void merge(List L1, List L2, Comparator c, List L) {
    while (!L1.isEmpty() && !L2.isEmpty())
      if (c.compare(L1.first().element(), L2.first().element()) <= 0)
        L.insertLast(L1.remove(L1.first()));
      else
        L.insertLast(L2.remove(L2.first()));
    while(!L1.isEmpty()) // move the remaining elements of L1
      L.insertLast(L1.remove(L1.first()));
    while(!L2.isEmpty()) // move the remaining elements of L2
      L.insertLast(L2.remove(L2.first()));
  }
  //end#fragment merge

  /**
   * Sort an array of objects with a comparator using nonrecursive merge sort.
   */
  //begin#fragment mergeSort2
  public static void mergeSort(Object[] orig, Comparator c) { // nonrecursive
    Object[] in = new Object[orig.length]; // make a new temporary array
    System.arraycopy(orig,0,in,0,in.length); // copy the input
    Object[] out = new Object[in.length]; // output array
    Object[] temp; // temp array reference used for swapping
    int n = in.length;
    for (int i=1; i < n; i*=2) { // each iteration sorts all length-2*i runs 
      for (int j=0; j < n; j+=2*i)  // each iteration merges two length-i pairs
        merge(in,out,c,j,i); // merge from in to out two length-i runs at j
      temp = in; in = out; out = temp; // swap arrays for next iteration
    }
    // the "in" array contains the sorted array, so re-copy it
    System.arraycopy(in,0,orig,0,in.length);
  }
  protected static void merge(Object[] in, Object[] out, Comparator c, int start, 
      int inc) { // merge in[start..start+inc-1] and in[start+inc..start+2*inc-1]
    int x = start; // index into run #1
    int end1 = Math.min(start+inc, in.length); // boundary for run #1
    int end2 = Math.min(start+2*inc, in.length); // boundary for run #2
    int y = start+inc; // index into run #2 (could be beyond array boundary)
    int z = start; // index into the out array
    while ((x < end1) && (y < end2)) 
      if (c.compare(in[x],in[y]) <= 0) out[z++] = in[x++];
      else out[z++] = in[y++];
    if (x < end1) // first run didn't finish
      System.arraycopy(in, x, out, z, end1 - x);
    else if (y < end2) // second run didn't finish
      System.arraycopy(in, y, out, z, end2 - y);
  }
  //end#fragment mergeSort2
      
  /**
   * Sort the elements of list L in nondecreasing order according to
   * comparator c, using a list-based implementation of the quicksort
   * algorithm.
   **/
  public static void quickSort(List L, Comparator c) {
    if (L.size() <= 1) 
      return;

    Object pivot = L.remove(L.last());

    List lesser = new NodeList();
    List equal = new NodeList();
    List greater = new NodeList();

    Object cur;
    while (!L.isEmpty()) {
      cur = L.remove(L.first());
      if (c.compare(cur,pivot) < 0)
	lesser.insertFirst(cur);
      else if(c.compare(cur,pivot) == 0)
	equal.insertFirst(cur);
      else
	greater.insertFirst(cur);
    }

    quickSort(lesser,c);
    quickSort(greater,c);

    while(!lesser.isEmpty())
      L.insertLast(lesser.remove(lesser.first()));
    while(!equal.isEmpty())
      L.insertLast(equal.remove(equal.first()));
    L.insertLast(pivot);
    while(!greater.isEmpty())
      L.insertLast(greater.remove(greater.first()));
  }


  /**
   * Sort the elements of array S in nondecreasing order according
   * to comparator c, using the quick-sort algorithm. Most of the work
   * is done by the auxiliary recursive method quickSortStep.
   **/
  //begin#fragment quickSort
  public static void quickSort (Object[] S, Comparator c) {
    if (S.length < 2) return; // the array is already sorted in this case
    quickSortStep(S, c, 0, S.length-1); // recursive sort method
  }
  //end#fragment quickSort
  
  /**
   * Sort in nondecreasing order the elements of sequence S between
   * ranks leftBound and rightBound, using a recursive, in-place,
   * implementation of the quick-sort algorithm.
   **/
  //begin#fragment quickSortStep
  private static void quickSortStep (Object[] S, Comparator c,
                              int leftBound, int rightBound ) {
    if (leftBound >= rightBound) return; // the indices have crossed
    Object temp;  // temp object used for swapping
    Object pivot = S[rightBound];
    int leftIndex = leftBound;     // will scan rightward
    int rightIndex = rightBound-1; // will scan leftward
    while (leftIndex <= rightIndex) { // scan right until larger than the pivot
      while ( (leftIndex <= rightIndex) && (c.compare(S[leftIndex], pivot)<=0) )
        leftIndex++; 
      // scan leftward to find an element smaller than the pivot
      while ( (rightIndex >= leftIndex) && (c.compare(S[rightIndex], pivot)>=0))
        rightIndex--;
      if (leftIndex < rightIndex) { // both elements were found
        temp = S[rightIndex]; 
	S[rightIndex] = S[leftIndex]; // swap these elements
	S[leftIndex] = temp;
      }
    } // the loop continues until the indices cross
    temp = S[rightBound]; // swap pivot with the element at leftIndex
    S[rightBound] = S[leftIndex]; 
    S[leftIndex] = temp; // the pivot is now at leftIndex, so recurse
    quickSortStep(S, c, leftBound, leftIndex-1);
    quickSortStep(S, c, leftIndex+1, rightBound);
  }
  //end#fragment quickSortStep
  
  public static void main (String[] argv) throws IOException {
    out("Start your engines...");
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    Random r = new Random();
    Comparator c = new DefaultComparator();
    out("Enter number of elements:");
    String num = in.readLine();
    int n = (new Integer(num)).intValue();
    String cont;
    Object[] A = new Integer[n];
    Object[] B = new Integer[n];
    float msin=0f,qsin=0f,msout=0f,qsout=0f;
    long t;
    do {
      List C = new NodeList();
      List D = new NodeList();
      for (int i = 0; i < n; i++) {
        int x = r.nextInt() % 100;
        A[i] = new Integer(x);
        B[i] = new Integer(x);
	C.insertLast(new Integer(x));
	D.insertLast(new Integer(x));
      }
      out("Array-Based Sorting");
      out("Before: " + Arrays.asList(A));

      //array-based mergesort
      t = System.currentTimeMillis();
      mergeSort(A, c);
      msin = (System.currentTimeMillis()-t)/1000f;
      out("MSort:  " + Arrays.asList(A));

      String correct = Arrays.asList(A).toString();

      //array-based quicksort
      t = System.currentTimeMillis();
      quickSort(B, c);
      qsin = (System.currentTimeMillis()-t)/1000f;
      out("QSort:  " + Arrays.asList(B));

      if(!correct.equals(Arrays.asList(B).toString())) {
	System.out.println("sorts produced different results!");
	System.exit(1);
      }

      out("List-Based Sorting");

      //list-based mergesort
      t = System.currentTimeMillis();
      mergeSort(C, c);
      out("MSort:  " + C);
      msout = (System.currentTimeMillis()-t)/1000f;

      if(!correct.equals(C.toString())) {
	System.out.println("sorts produced different results!");
	System.exit(1);
      }

      //list-based quicksort
      t = System.currentTimeMillis();
      quickSort(D, c);
      out("QSort:  " + D);
      qsout = (System.currentTimeMillis()-t)/1000f;

      if(!correct.equals(D.toString())) {
	System.out.println("sorts produced different results!");
	System.exit(1);
      }
      
      out("Times (in seconds)");
      out("Array-Based");
      out("MSort:  "+msin);
      out("QSort:  "+qsin);
      out("List-Based");
      out("MSort:  "+msout);
      out("QSort:  "+qsout);

      out("Type 'e' to end ...");
      cont = in.readLine();
    } while (cont.equals(""));
  } 
  
  private static void out (String s) {
    System.out.println(s);
  }
}
